home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / 5col.c next >
C/C++ Source or Header  |  1994-08-05  |  8KB  |  363 lines
  1. #include <LEDA/graph_edit.h>
  2. #include <LEDA/ugraph.h>
  3. #include <LEDA/stack.h>
  4. #include <LEDA/array.h>
  5.  
  6. window win;
  7.  
  8. bool trace;
  9. bool step;
  10.  
  11. #if !defined(__TEMPLATE_FUNCTIONS__)
  12. int compare(list<node>&, list<node>&) { return 0; }
  13. LEDA_TYPE_PARAMETER(list<node>)
  14. #endif
  15.  
  16.  
  17. void FIND_INDEPENDENT_NEIGHBORS(const ugraph& G, const node_array<int>&, 
  18.                                 node v, node& u, node& w);
  19.  
  20. int  UNUSED_ADJ_COLOR(node v, const node_array<int>& col);
  21.  
  22.  
  23. void FIVE_COLOR(const GRAPH<point,int>& G, node_array<int>& C)
  24. {
  25.   // G is a planar graph
  26.  
  27.   UGRAPH<point,int> G1;
  28.  
  29.  
  30.  
  31.   G1 = G;
  32.  
  33.   //we have to avoid parallel edges
  34.  
  35.  
  36.   node_array<int>  C1(G1,0);       // C1[v] = color of node v in G1
  37.   node_array<bool> mark(G1,false);
  38.   node_array<int>  deg(G1);        // deg[v] = current degree of v
  39.  
  40.   list<node> small_deg;            // list of nodes with deg[v] <= 5
  41.   node_array<list_item> I(G1,nil); // I[v] = location of v in small_deg
  42.  
  43.   node_array<list<node> > L(G1);   // L[v] = list of nodes of G represented by v
  44.  
  45.   stack<node>  removed;            // stack of (conceptually) removed nodes
  46.  
  47.   int N;                           // current number of valid nodes of G1
  48.  
  49.  
  50.   // Initialization
  51.  
  52.   N = G1.number_of_nodes();
  53.  
  54.   node u,v,w,x;
  55.  
  56.   u = G.first_node();
  57.  
  58.   forall_nodes(v,G1)
  59.   { deg[v] = G1.degree(v);
  60.     if(deg[v] <= 5) I[v] = small_deg.append(v);
  61.     L[v].append(u);
  62.     u = G.succ_node(u);
  63.    }
  64.  
  65.   // shrinking G1
  66.  
  67. if (trace) win.message("shrinking graph G ---> G1");
  68.  
  69.   while (N > 0)
  70.   {
  71.     forall_nodes(v,G1)
  72.     { int d = 0;
  73.       forall_adj_nodes(x,v) if (C1[x] != -1) d++;
  74.       if (C1[v] != -1 && deg[v] != d) 
  75.       { win.draw_filled_node(G1[v]); 
  76.         error_handler(1,string("N = %d  deg = %d   d = %d",N,deg[v],d));
  77.        }
  78.      }
  79.  
  80.     if (small_deg.empty())
  81.        error_handler(1,"smalldeg is empty");
  82.  
  83.     v = small_deg.pop();
  84.  
  85.     I[v] = nil;
  86.  
  87.     if (trace) 
  88.     { win.set_mode(xor_mode);
  89.       win.draw_text_node(G1[v],"?");
  90.       win.draw_filled_node(G1[v]);
  91.       win.set_mode(src_mode);
  92.      }
  93.  
  94.     if (deg[v] == 5)
  95.     {
  96.       FIND_INDEPENDENT_NEIGHBORS(G1,C1,v,u,w);
  97.  
  98.       if (w == u) error_handler(1,"merging identical nodes"); //parallel edges
  99.  
  100.       if(trace)
  101.       { win.set_mode(xor_mode);
  102.         win.draw_text_node(G1[w],"?");
  103.         win.draw_filled_node(G1[w]);
  104.         win.draw_filled_node(G1[u]);
  105.         win.draw_edge(G1[v],G1[u]);
  106.         win.draw_edge(G1[v],G1[w]);
  107.         win.set_line_width(2);
  108.         win.draw_edge(G1[v],G1[u]);
  109.         win.draw_edge(G1[v],G1[w]);
  110.         if (step) win.read_mouse();
  111.         win.draw_edge(G1[v],G1[u]);
  112.         win.draw_edge(G1[v],G1[w]);
  113.         win.set_line_width(1);
  114.         win.draw_edge(G1[v],G1[u]);
  115.         win.draw_edge(G1[v],G1[w]);
  116.         win.draw_filled_node(G1[v]);
  117.         win.draw_node(G1[v]);
  118.        }
  119.  
  120.       { forall_adj_nodes(x,u) mark[x] = true; }
  121.  
  122.       forall_adj_nodes(x,w)
  123.       { if (x == u) error_handler(1,"merging adjacent nodes");
  124.         if (mark[x]) 
  125.            { deg[x]--;
  126.              if (deg[x] == 5) 
  127.                 I[x] = small_deg.append(x);
  128.             }
  129.         else
  130.            { G1.new_edge(u,x,0);
  131.              if (C1[x] != -1) deg[u]++;  
  132.              if(trace) win.draw_edge(G1[u],G1[x]);
  133.             }
  134.        }
  135.  
  136.       { forall_adj_nodes(x,u) mark[x] = false; }
  137.  
  138.       deg[v]--;
  139.  
  140.  
  141.       if (deg[u] > 5 && I[u] != nil)
  142.       { small_deg.del(I[u]);
  143.         I[u] = nil;
  144.        }
  145.  
  146.       L[u].conc(L[w]);
  147.      
  148.       if (I[w] != nil) small_deg.del(I[w]);
  149.  
  150.  
  151.       if (trace)
  152.       { forall_adj_nodes(x,w) win.draw_edge(G1[w],G1[x]);
  153.         win.draw_filled_node(G1[w]);
  154.         win.draw_filled_node(G1[u]);
  155.         win.set_mode(src_mode);
  156.        }
  157.  
  158.       G1.del_node(w);
  159.  
  160.       N--;
  161.  
  162.     }
  163.  
  164.     if (step)  win.read_mouse();
  165.  
  166.     //  now deg[v] <= 4
  167.  
  168.     C1[v] = -1;
  169.     removed.push(v);
  170.  
  171.     forall_adj_nodes(x,v)
  172.        if ( --deg[x] == 5) 
  173.          I[x] = small_deg.append(x);
  174.  
  175.     N--;
  176.    }
  177.  
  178. if (trace)
  179. { win.read_mouse();
  180.   win.del_message();
  181.   win.message("coloring G1");
  182. }
  183.  
  184.  
  185.    // now color the nodes in "removed" from top to bottom
  186.  
  187.    while ( ! removed.empty() )
  188.    { v = removed.pop();
  189.  
  190.      int c = UNUSED_ADJ_COLOR(v,C1);
  191.  
  192.      if (c == 5) error_handler(1,"more than 5 different adjacent colors");
  193.  
  194.      C1[v] = c;
  195.      forall(x,L[v]) C[x] = c;
  196.  
  197.      if (trace) win.draw_int_node(G1[v],c);
  198.      if (step)  win.read_mouse();
  199.  
  200.     }
  201.  
  202.  
  203.     if (trace) 
  204.     { edge e;
  205.       win.read_mouse();
  206.       win.del_message();
  207.       win.message("coloring G");
  208.       win.set_mode(xor_mode);
  209.       forall_edges(e,G1) win.draw_edge(G1[source(e)],G1[target(e)]);
  210.       win.set_mode(src_mode);
  211.      }
  212. }
  213.  
  214.  
  215.      
  216. void  FIND_INDEPENDENT_NEIGHBORS(const ugraph& G, const node_array<int>& col,
  217.                                  node v, node& u, node& w)
  218. { node x;
  219.   list<node> L;
  220.  
  221.   forall_adj_nodes(x,v)
  222.       if (col[x] != -1) L.append(x);
  223.  
  224.   for (list_item it1 = L.first(); it1 != nil; it1 = L.succ(it1))
  225.     { u = L[it1];
  226.       for (list_item it2 = L.succ(it1); it2 != nil; it2 = L.succ(it2))
  227.         { w = L[it2];
  228.           forall_adj_nodes(x,w) if (x == u) break;
  229.           G.init_adj_iterator(w);
  230.           if (x != u) return;
  231.          }
  232.      }
  233.  
  234.   error_handler(1,"no independent neighbors found!");
  235.   return;
  236.  }
  237.  
  238.  
  239. int UNUSED_ADJ_COLOR(node v, const node_array<int>& col)
  240. { 
  241.   int used[6];
  242.   int c;
  243.   node x;
  244.  
  245.   for(c = 0; c < 6; c++) used[c] = 0;
  246.  
  247.   forall_adj_nodes(x,v)
  248.   { c = col[x];
  249.     if (c != -1) used[c] = 1;
  250.    }
  251.  
  252.   c = 0; 
  253.   while(used[c]) c++;
  254.  
  255.   return c;
  256.  }
  257.  
  258.  
  259.  
  260. void grid_graph(GRAPH<point,int>& G, int n, float win_width)
  261. {
  262.   array2<node>  A(n,n);
  263.   float dist = win_width/(n+3);
  264.   int i,j;
  265.  
  266.   G.clear();
  267.  
  268.   for(i=0; i<n; i++)
  269.     for(j=0; j<n; j++)
  270.       A(i,j) = G.new_node(point(dist*(j+2),dist*(i+2)));
  271.  
  272.  
  273.   for(i=0; i<n; i++)
  274.     for(j=0; j<n; j++)
  275.        { if (i < n-1) G.new_edge(A(i,j),A(i+1,j));
  276.          if (j < n-1) G.new_edge(A(i,j),A(i
  277. ,j+1));
  278.          if (i < n-1 && j < n-1) G.new_edge(A(i,j),A(i+1,j+1));
  279.         }
  280.  
  281.   node north = G.new_node(point(dist*((n-1)/2.0 + 2),dist*(n+2)));
  282.   node south = G.new_node(point(dist*((n-1)/2.0 + 2),dist));
  283.   node west  = G.new_node(point(dist,dist*((n-1)/2.0 + 2)));
  284.   node east  = G.new_node(point(dist*(n+2),dist*((n-1)/2.0 + 2)));
  285.  
  286.   for(i=0; i < n; i++)
  287.   { G.new_edge(north,A(n-1,i));
  288.     G.new_edge(south,A(0,i));
  289.     G.new_edge(west,A(i,0));
  290.     G.new_edge(east,A(i,n-1));
  291.    }
  292.   
  293.   //G.new_edge(A(0,n-1),A(n-1,0));
  294.  
  295. /*
  296.   list<edge> E = G.all_edges();
  297.   edge e;
  298.   forall(e,E) G.new_edge(target(e),source(e));
  299. */
  300.  
  301. }
  302.  
  303.          
  304. char* COLOR[] = {"blue","red","green","violet","orange"};
  305.     
  306. main()
  307. {
  308.   GRAPH<point,int>  G;
  309.   node v;
  310.   edge e;
  311.  
  312.  
  313.  
  314.   int n = 8;
  315.   int t = 0;
  316.  
  317.   win.init(0,1000,0);
  318.   win.set_node_width(10);
  319.  
  320.   panel P("five coloring a planar graph");
  321.  
  322.   P.choice_item("trace",t,"off","step","movie");
  323.   P.int_item("N = ",n,1,30);
  324.   P.button("edit");
  325.   P.button("grid");
  326.   P.button("quit");
  327.  
  328.   for(;;)
  329.   { 
  330.  
  331.     int inp = P.open(win);
  332.     
  333.     trace = (t > 0);
  334.     step  = (t == 1);
  335.  
  336.     if (inp == 2) break;
  337.  
  338.     win.clear();
  339.  
  340.     if (inp == 0) graph_edit(win,G,false);
  341.    
  342.     if (inp == 1) grid_graph(G,n,1000);
  343.  
  344.     forall_nodes(v,G) win.draw_text_node(G[v],"?");
  345.     forall_edges(e,G) win.draw_edge(G[source(e)],G[target(e)]);
  346.  
  347.     node_array<int> col(G,-1);
  348.  
  349.     FIVE_COLOR(G,col);
  350.  
  351.     forall_edges(e,G) win.draw_edge(G[source(e)],G[target(e)]);
  352.     forall_nodes(v,G) win.draw_int_node(G[v],col[v],col[v]+2);
  353.  
  354.     win.set_frame_label("click any button to continue");
  355.     win.read_mouse();
  356.     win.reset_frame_label();
  357.  
  358.   }
  359.  
  360.   return 0;
  361.  
  362. }
  363.